1511. Разрезание торта
Имеется
прямоугольный торт длины length и
ширины width. Мы хотим разрезать его
на pieces прямоугольных кусков равной
площади. Каждый разрез должен совершаться параллельно сторонам торта, и должен
полностью разрезать один из имеющихся кусков на две части. (Для разрезания
торта на n кусков необходимо
совершить n – 1 разрез)
Квадратные куски
Вы предпочитаете тем, которые имеют большее отношение сторон. Под “отношением
сторон” будем понимать отношение длины большей стороны куска к меньшей. Вам
следует разрезать торт таким образом, чтобы минимизировать максимальное
значение отношения сторон полученных кусков.
Например, если
мы хотим разрезать торт 2x3 на шесть кусков, то это можно сделать, разрезав его
на шесть кусков размера 1x1. Отношение
сторон каждого куска равно 1.0, что является наименьшим возможным. Поэтому
решение оптимально.
Один из
возможных вариантов разрезать торт 5x5 на 5 кусков состоит в следующем: сначала
разрезаем торт на две части размерами 2x5 и 3x5. Меньшую часть делим пополам
(получаем две части размером 2 x 5/2), а большую часть делим на три части
(каждая имеет размер 3 x 5/3). Большее отношение сторон достигается на куске 3 x
5/3 и равно 3/(5/3) = 1.8. Разделить торт на 5 частей равной площади с меньшим
отношением сторон, нежели 1.8 невозможно.
Вход. Состоит из нескольких тестов, каждый из которых задается
в одной строке и содержит три целых числа: длину length
и ширину width торта, а также
количество прямоугольных кусков pieces,
на которое следует разрезать торт. Известно, что 1 ≤ length, width ≤
1000, 1 ≤ pieces ≤ 10.
Выход. Следует разрезать торт так, чтобы минимизировать
максимальное значение отношения сторон полученных кусков. Для каждого теста
вывести в отдельной строке полученное отношение сторон с 4 десятичными
цифрами. Помните, что все полученные куски должны иметь одинаковую площадь!
|
Пример
входа |
Пример
выхода |
|
2 3 6 5 5 5 950 430 9 |
1.0000 1.8000 1.2573 |
РЕШЕНИЕ
рекурсия + полный перебор
Анализ алгоритма
Благодаря
верхнему ограничению на число кусков pieces,
задача может быть просто решена полным перебором разрезаний торта. Если кусок
размером length на width следует разбить на pieces кусков, то после совершения первого
разреза (который по условию задачи можно совершить либо по горизонтали, либо по
вертикали) площади двух полученных кусков должны быть пропорциональны числам 1
и pieces – 1, или 2 и pieces – 2 и так далее. То есть после
первого разреза должны получаться два куска размером i * length / pieces на width и ((pieces – i ) * length / pieces на width, или length на i * width / pieces и length на (pieces – i) * width / pieces, где 1 £ i < pieces. При этом дальше первый кусок
следует делить на i кусков, а второй
на pieces – i кусков.
Совершаем разрез
исходного куска на две части и далее рекурсивно запускаем разрезание каждой из
полученных частей. Ищем такое разрезание, при котором максимум отношения кусков
является наименьшим.
Реализация алгоритма
Функция cut возвращает наименьшее возможное максимальное значение
отношения сторон полученных pieces кусков в результате разрезания прямоугольника длины length и ширины width.
double cut(double
length, double width, int
pieces)
{
double temp,
res = 1e100;
int i;
Если pieces равно 1, то возвращаем отношение сторон текущего куска.
if (pieces ==
1) return max(length,width) /
min(length,width);
Совершаем вертикальный разрез торта
на две части, каждая из которых дальше будет делиться на i и pieces – i кусков.
for(i = 1; i
< pieces; i++)
{
temp = max(cut(i * length /
pieces,width,i),
cut((pieces - i) * length /
pieces,width,pieces - i));
if (temp
< res) res = temp;
}
Совершаем горизонтальный разрез торта
на две части, каждая из которых дальше будет делиться на i и pieces – i кусков.
for(i = 1; i
< pieces; i++)
{
temp = max(cut(length,i * width /
pieces,i),
cut(length,(pieces - i) * width
/ pieces,pieces - i));
if (temp
< res) res = temp;
}
return res;
}
Основной цикл программы.
while(scanf("%d
%d %d",&length, &width, &pieces) == 3)
{
double res =
cut(length,width,pieces);
printf("%.4lf\n",res);
}
Временная оценка
работы алгоритма
Пусть f(pieces) – функция, которая возвращает количество вызовов функции
cut в зависимости от значения pieces.
Очевидно, что f(1) = 1, так как в этом случае сразу после
вызова функции выйдем по команде return.
При pieces = 2 первый вызов функции cut будет со
значением pieces = 2. Далее
кусок будем стараться разделить пополам вертикальным разрезом, в результате
чего дважды будет вызвана f(1). Потом попробуем совершить горизонтальный
разрез, снова будет дважды вызвана f(1). Итого получим f(2) = 5 вызовов функции
cut.
Пусть pieces = 3. Первый вертикальный разрез разобьет кусок на две
части, первый из которых далее надо будет делить на 1 часть, а второй на 2
части. Второй вертикальный разрез также разобьет кусок на две части, первый из
которых далее надо будет делить на 2 части, а второй на 1 часть. Аналогичное
количество вызовов функции следует произвести при горизонтальных разрезах.
Итого
f(3) = 1 + 2 * ( (f(1) + f(2) ) + (f(2) + f(1)) ) = 1 + 2 * 2 * (1 + 5) = 25
В общем случае f(n)
= 1 + 
= 1 + 
.
Например:
f(4) = 1 + 
= 1 + 4 * (1 + 5 + 25)
= 125,
f(5) = 1 + 
= 1 + 4 * (1 + 5 + 25
+ 125) = 625
Докажем методом
математической индукции, что f(n) = 5n-1.
База индукции. f(1) = 50 = 1.
Шаг индукции. f(n) = 1 + = 1 + 4 (50
+ 51 + … + 5n-2)
= 1 + 
= 5n-1.
Временная оценка работы программы составляет O(5pieces).
Java реализация
import java.util.*;
import java.io.*;
public class Main
{
public static double cut(double length, double width, int pieces)
{
double temp, res = 1e100;
int i;
if (pieces == 1)
return Math.max(length,width)
/ Math.min(length,width);
for(i = 1; i < pieces; i++)
{
temp = Math.max(cut(i *
length / pieces,width,i),
cut((pieces - i) * length /
pieces,width,pieces - i));
if (temp < res) res = temp;
}
for(i = 1; i < pieces; i++)
{
temp = Math.max(cut(length,i
* width / pieces,i),
cut(length,(pieces - i) *
width / pieces,pieces - i));
if (temp < res) res = temp;
}
return res;
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
PrintWriter out = new
PrintWriter(System.out,true);
while(con.hasNextInt())
{
int length =
con.nextInt(),
width = con.nextInt(),
pieces = con.nextInt();
double res = cut(length,width,pieces);;
out.printf(Locale.US,"%.4f\n",res);
}
}
}